package com.xw.class10;

import java.util.Stack;

/**
 * @author XW
 * @data 2023/7/3 16:15
 * @description非递归遍历二叉树
 */
public class Code03_UnRecursiveTraversalBT {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int v) {
            value = v;
        }
    }

    public static void pre(Node cur){
        System.out.println("前序打印：");
        if(null != cur){
            Stack<Node> stack = new Stack<>();
            stack.push(cur);
            while(!stack.isEmpty()){
                cur = stack.pop();
                System.out.print(cur.value + " ");

                if(cur.right != null){
                    stack.push(cur.right);
                }
                if(cur.left != null){
                    stack.push(cur.left);
                }
            }
        }
        System.out.println();
    }

    /**
     * 中序遍历的思路
     *  只要当前节点不为null 或者栈不为空 ：
     *  1）把当前节点的左节点加入栈，当前节点变为其左节点，直到当前节点为null,
     *  2)弹出栈顶元素，变为当前节点， 打印输出，当前节点变为其右节点
     * @param cur
     */
    public static void in(Node cur){
        System.out.println("中序遍历：");
        if(null != cur){
            Stack<Node> stack = new Stack<>();
            while (!stack.isEmpty() || cur != null){
                if(null != cur){
                    stack.push(cur);
                    cur = cur.left;
                }else {
                    cur = stack.pop();
                    System.out.print(cur.value +" ");
                    cur = cur.right;
                }
            }
        }
        System.out.println();
    }

    /**
     * 后续遍历 准备两个栈 第一个栈弹出的顺序为 头 右 左
     * 然后将弹出的元素加入第二个栈，最后弹出即为后续遍历
     *
     * @param cur
     */
    public static void pos1(Node cur){
        System.out.println("后续遍历 ：");
        if(null != cur){
            Stack<Node> s1 = new Stack<>();
            Stack<Node> s2 = new Stack<>();
            s1.push(cur);
            while(!s1.isEmpty()){
                cur = s1.pop();
                s2.push(cur);
                if(cur.left != null){
                    s1.push(cur.left);
                }
                if(cur.right != null){
                    s1.push(cur.right);
                }
            }
            while (!s2.isEmpty()){
                System.out.print(s2.pop().value + " ");
            }
        }
    }

    public static void post2(Node cur){
        System.out.println("post2:");

    }


    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);

        pre(head);
        System.out.println("========");
        in(head);
        System.out.println("========");
//        pos1(head);
//        System.out.println("========");
//        pos2(head);
//        System.out.println("========");
    }

}
